1. Field of the Invention
The present invention is related to a Local Area Network (LAN) employing the Carrier Sense, Multiple Access with Collision Detection (CSMA/CD) Media Access Control (MAC) protocol, such as an IEEE standard 802.3 LAN or Ethernet LAN, hereafter collectively referred to as a CSMA/CD based LAN, or simply, CSMA/CD LAN. More specifically, the present invention is related to a repeating device, such as a repeater or hub, providing for deterministic access in a CSMA/CD LAN for up to and including 15 nodes each connected to the repeating device by way of a communication medium The repeating device further provides for a relatively shorter average media access latency than that provided by a prior art repeating device for a CSMA/CD LAN supporting greater than 15 nodes each connected to the repeating device by way of a communication medium.
2. Description of the Related Art
Ethernet and IEEE 802.3 are Local Area Network (LAN) standards that utilize the well known Carrier Sense, Multiple Access with Collision Detection (CSMA/CD) Media Access Control (MAC) protocol. The CSMA/CD MAC protocol provides an access method by which nodes connected to a shared communication medium may access the medium. Nodes are physically connected to the shared communication medium by way of what is commonly referred to as a Network Interface Card (NIC) or adapter. In a CSMA/CD LAN, a node's adapter contains means for communicating with other nodes according to the CSMA/CD MAC protocol. Two types of adapters are commonly utilized in CSMA/CD LANs: Ethernet adapters and IEEE 802.3 adapters. An Ethernet adapter supports transmitting and receiving Ethernet data packets in accordance with the CSMA/CD protocol, whereas an IEEE 802.3 adapter supports transmitting and receiving IEEE 802.3 data packets in accordance with the CSMA/CD protocol.
The initial communication medium used in a CSMA/CD LAN was a shared coaxial cable to which all nodes were attached in a bus topology. 10BASE5 and 10BASE2 provide the IEEE 802.3 Physical Layer specifications for a 10 million bits per second (Mbps) CSMA/CD LAN over coaxial cable. (See IEEE 802.3 clauses 8 and 10.) Such LANs were extended by connecting multiple communication medium segments together through one or more repeaters. However, the standards have evolved such that, today, a LAN is typically comprised of one or more hubs each providing a point-to-point connection to one of a plurality of nodes via a communication medium, such as twisted pair telephone wiring or fiber-optic cable, in a star wired topology. 10BASE-T and 10BASE-F provide the IEEE 802.3 Physical Layer specifications for a 10 Mbps CSMA/CD LAN over twisted pair wiring and fiber optic cable, respectively. (See IEEE 802.3 clauses 14 and 15.)
A repeating device such as a repeater or hub provides repeating functionality between the nodes connected to the repeating device. Hereafter, the term repeater will be used to refer to the repeating device but it is understood that the term repeater as used herein includes both repeater and hub devices. The repeater connects multiple communication medium segments to form a single shared communication medium in which all nodes on all of the communication medium segments are peers such that only one node may successfully transmit a data packet at a time. Since the repeater provides a common shared communication medium between all communication medium segments connected to the repeater, when any two or more nodes in the LAN attempt to transmit a data packet simultaneously, a collision occurs according to the CSMA/CD MAC protocol. Thus, in a CSMA/CD LAN utilizing one or more repeaters, all nodes in the LAN are said to be in the same collision domain. Each node involved in a collision stops transmitting their data packet and waits a period of time known as the backoff time before attempting to retransmit the same data packet. Each node determines its backoff time from a random number generator. If a node detects a collision on 16 consecutive retransmission attempts, then the data packet is discarded.
CSMA/CD LANs have had tremendous commercial success in the data communications market. However, one of the limitations of such LANs is the random backoff time that occurs when a node detects a collision according to the CSMA/CD MAC protocol. The media access latency experienced by a node in a CSMA/CD LAN, i.e., the delay incurred in an adapter receiving a data packet from a node and actually transmitting the data packet on to the medium, can be extremely variable and potentially very long depending on the random backoff time. Indeed, the media access latency may be infinite if the data packet is discarded due to excessive collisions.
Because a data packet may be discarded by a node in a CSMA/CD LAN due to excessive collisions, CSMA/CD LANs are said to be non-deterministic, indicating delivery of data is not guaranteed. The non-deterministic aspect of the access method employed by CSMA/CD LANs has limited the market acceptance of such LANs for delay sensitive applications such as factory automation, process control, real time voice and video traffic, and interactive multimedia.
What is needed is a LAN employing a media access method that guarantees delivery of data. Such an access method is said to be a deterministic access method because the maximum media access latency that a node may experience can be definitively determined. Prior attempts to provide for a deterministic media access method for nodes in a CSMA/CD LAN have focused on two approaches: (i) modify the random backoff time algorithm in the adapter associated with a node in order to coordinate retransmission attempts between nodes in a manner that reduces the likelihood of a particular node experiencing multiple consecutive collisions; and (ii) modify both the repeater(s) in the LAN and the adapter in each node so that collisions are avoided. The latter approach necessarily requires using means other than the CSMA/CD MAC protocol to arbitrate for the communication medium
A number of the prior art methods and apparatus addressing the non-deterministic limitations of the CSMA/CD MAC protocol have centered around modifying the random backoff time algorithm utilized by the adapter installed in the nodes coupled to the LAN. The modified backoff time algorithms include the: (i) Binary Logarithmic Access Method (BLAM); (ii) Capture Avoidance Binary Exponential Backoff (CABEB) developed by Digital Equipment Corporation (DEC); and (iii) Priority Access Controlled Ethernet (PACE) developed by 3Com Corporation.
A disadvantage of the prior approaches to providing a deterministic media access method in a CSMA/CD LAN is that they require modifying the CSMA/CD MAC protocol as implemented in the adapter associated with each node in the LAN. Modifying the CSMA/CD MAC protocol creates its own set of problems. First, an adapter for use in a CSMA/CD LAN is manufactured according to an international standard (IEEE 802.3 and ISO 8802.3) or the de facto Ethernet standard, both of which specify use of the CSMA/CD MAC protocol. Therefore, any deviation from the standards involving modification of the CSMA/CD MAC protocol is likely to violate the standards and is thus likely to cause interoperability problems for nodes in which an adapter having a modified CSMA/CD MAC protocol is installed. For example, a node having an adapter operating in accordance with the CSMA/CD MAC protocol as specified by the IEEE 802.3 standard may not be able to communicate with a node having a non-standard adapter operating in accordance with a non-standard media access control protocol. Additionally, there is a very significant installed base of nodes having Ethernet and/or IEEE 802.3 compliant adapters that do not have the modifications necessary to provide deterministic access, and thus cannot benefit from the prior approaches. Therefore, what is needed is a deterministic access method for a CSMA/CD LAN that does not require modifying the CSMA/CD MAC protocol in a node's adapter.
Recently, the concept of a buffered repeater has been presented at study group meetings of the IEEE 802.3 standards Working Group by a representative of Packet Engines, Incorporated, as part of a collaborative effort involving several companies. Although both the preferred embodiment of the present invention and the buffered repeater buffer data, they differ significantly in both their objectives and their operation. The objective of the prior art buffered repeater is to extend the maximum distance between a node and a repeater in CSMA/CD LAN without increasing the slot time parameter of the LAN, but does so by removing the CSMA/CD MAC protocol in the adapter at the node, whereas an object of the present invention is to control media access latency for a node without modifying the MAC protocol utilized by the adapter in the node.
Thus, what is needed is a method and apparatus for a node to access the medium in a CSMA/CD LAN that does not require modifying the backoff algorithm or any other component of the adapter in the node. Furthermore, what is needed is a repeater that provides deterministic access in a CSMA/CD LAN for up to and including 15 nodes, and a relatively shorter average communication media access latency than possible in the prior art for a CSMA/CD LAN with more than 15 nodes.